package com.syygl.test.study.leetCode;


/**
 * 链表排序
 * 快慢指针法，遍历链表找到中间节点、中间节点切断链表
 * 分别用归并排序排左右子链表、合并子链表
 */
class LinkedListSolution {
    public ListNode sortList(ListNode head) {
        //如果链表为空，或者只有一个节点，直接返回即可，不用排序
        if (head == null || head.next == null)
            return head;
        //快慢指针移动，以寻找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //找到中间节点，slow节点的next指针，指向mid
        ListNode mid = slow.next;
        //切断链表
        slow.next = null;
        //排序左子链表
        ListNode left = sortList(head);
        //排序右子链表
        ListNode right = sortList(mid);
        //合并链表
        return merge(left, right);
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode head = new ListNode(0);
        ListNode temp = head;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        if (left != null) {
            temp.next = left;
        }
        if (right != null) {
            temp.next = right;
        }
        return head.next;
    }
}

class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}


class Test{
    public ListNode sortLinkedList(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        ListNode left = sortLinkedList(head);
        ListNode right = sortLinkedList(mid);

        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        if(left == null) return right;
        if(right == null) return left;
        ListNode head = null;
        if(left.val <= right.val){
            head = left;
            head.next = merge(left.next, right);
        }else {
            head = right;
            head.next = merge(left, right.next);
        }

        return head;

    }


}



























